Typically included in a computer system or computer network are (i) a digital processor, (ii) one or more workstations each defined by at least one display monitor (CRT), a keyboard and/or mouse, and (iii) a common printer (i.e., a printer to which users have access from the workstations). Users at respective workstations generate output to various locations, for instance internal memory files for storage, the workstation CRT for viewing on the video screen thereof, or the printer for a so called "hard copy" printout of the output information. As more and more users depend on hard copy printouts of computer generated information, greater desires exist for increased detail and accuracy in printing from the printer.
Generally, laser printers are among the more technically advanced printers of today and evolved from two other forms of printing, namely xerography and dot matrix printing, in response to the growing desire for more detailed and accurate printing. While xerography is a form of electrophotography in which an image is transferred from light to paper, dot matrix printing utilizes groups of dots to form geometric elements. As a result, today's laser printers usually accept orthogonal bitmaps of binary data. The laser beam is swept across the page as the page is rolled through the printer, modulating one row of data (a scan line) per pass. During each scan line, the paper is moved forward one pixel width. To obtain a quality result, it is important to produce pixels of consistent small size and shape at a correct location on the page being printed, corresponding to the bitmap data. Many advances have been made in decreasing the pixel size and refining its shape to be more uniform and square.
Most new advances in printers today focus on increasing the resolution, since it is relatively easy to form uniform dots. Common laser printers today are capable of printing 300 pixels per inch in both directions. However, increasing resolution has its costs; the memory required to hold one page of bitmap data increased from 60,000 bytes in a typical 72 DPI dot matrix printer to more than 1,000,000 bytes in a 300 DPI laser printer. Increasing resolution has serious repercussions on the amount of memory used to store bitmap images and the bandwidth required of printers to produce images at the same speed and cost.
Further, the quality of the printer output may be increased without increasing the resolution by a technique called "antialiasing". This technique has its basis in discrete time signal processing; it is a filtering technique to remove high frequency edges from pictures. To that end, in antialiasing, the high frequency components are filtered out of the printout (via a low pass filter and the like) and smoother edges result. The resulting image must then be printed on a grayscale capable printer. Thus antialiasing provides a method of increasing the effective resolution without increasing the pixel spacing.
As used herein "grayscaling" refers to the ability of an output device to produce shades of gray. That term is not to be confused with the term "halftoning" which is the process whereby intermediate shades of gray are produced by arranging patterns of lighter and darker pixels.
However, laser printers are designed to print bitonally, i.e., are supported by a bitmap whose pixels are either on (black) or off (white). This being the case, modifications must be made to the print engine to allow grayscale data to be printed. Although traditional methods of antialiasing can be used to generate grayscale pictures for the printer, many existing computer applications (programs) do not support antialiased output (i.e. such applications only form a bitonal bitmap of the output). In addition, most antialiasing methods belong to one of two categories of filters, prefilters and postfilters. A prefilter is employed to low pass filter output data before the data is scan converted into a bitmap. A postfilter is used to low pass filter output data after scan conversion of the data.
One example of a post filter is "supersampling". In supersampling the subject image (output data) is drawn bitonally (scan converted) on a supersampled grid, i.e. a high resolution bitmap. After the output data is scan converted, a filter is mapped across the supersampled image (high resolution bitmap) and combines clusters of samples to form grayscale pixels. The disadvantage of supersampling is that it is computationally expensive and extremely time consuming.
A prefilter version of supersampling is "area sampling". In this method, area computations are performed directly from subject output (image) data before scan conversion of the data to a high resolution bitmap. Since the grayscale values result directly from the subject output data, area sampling yields highly accurate results. However, overlapping objects become a serious problem in area sampling. In supersampling, the scan conversion takes care of overlapping areas by mapping them onto the same supersampled pixels. However, in area sampling, all objects must be considered simultaneously to resolve such conflicts. Otherwise, overlapping areas from different objects would be counted twice in computing grayscale value of the corresponding pixel.
Other antialiasing methods include the Gupta-Sproull antialiased scan conversion for lines. See "Filtering Edges for Grayscale Displays", by S. Gupta and R. F. Sproull, in Computer Graphics, 15(3): pages 1-5, August, 1981. Gupta-Sproull antialiasing uses the endpoints of a line and a pixel filter function to approximate antialiasing. In particular, a table of grayscale values is computed by performing an integration (convolution) over the intersection of a conical filter and a one-pixel wide line. Scan conversion of arbitrary lines is then performed using an incremental algorithm, similar to Bresenham's line drawing routine. J. E. Bresenham's line drawing routine is given in "Algorithm for Computer Control of a Digital Plotter", IBM Systems Journal, 4(1): pages 25-30, July, 1965. The Gupta-Sproull algorithm is also easily adapted to antialias polygon edges and endpoints of a line by using different tables.
Few general curve antialiasing routines exist. One such method is Turner Whitted's method of using antialiased brushes to draw arbitrary curves. See "Antialias Line Drawing Using Brush Extension", by Turner Whitted, in Computer Graphics, 17(3): pages 151-156, July, 1983. Briefly, the brush is first constructed at high resolution (i.e. a supersampled bitmap) and then digitally filtered to reduce the component frequencies to below the Nyquist rate of the drawing. Each pixel of the brush is additionally tagged with a depth (z), which prevents it from being overwritten by less important pixels as the brush moves incrementally across the page. The supersampled brush is then dragged across the page, but only the brush pixels which exactly coincide with the lower resolution page pixels are copied to the page. A generic z-buffer algorithm is used to determine if the page pixel should actually be updated. There are several disadvantages to antialiased brushes. For every different type of a line a different brush is needed, so libraries of brushes must be kept. Additionally the z-buffer algorithm is computationally expensive; the brush must have 3 or 4 bits of depth information per pixel to operate properly.
When displaying fonts, it is time consuming to antialias each letter as it is scan converted. Fonts are especially difficult because each character is both complex, consisting of possibly dozens of strokes, and interconnected. Rather than antialias during scan conversion, it is typically better to store grayscale antialiased copies of the font in arrays and simply copy (bit-blit) the characters to the video memory. See "The Display of Characters Using Gray Level Sample Arrays", by John E. Warnock, in Computer Graphics, 14(3): pages 302-307, July, 1980. However, a common problem with scan converting fonts occurs when the output resolution (pixel spacing) is too course to properly position the glyphs. Proper subpixel positioning can be achieved by storing various different positioned fonts in separate arrays, and bit blitting from the correctly subpositioned font array. Thus, this method has the disadvantage of using a large amount of memory.
Another antialiasing algorithm, scan converts antialiased polygons using a table lookup to draw antialiased edges. For each pixel, the pixel edge-polygon edge intersections are computed, and these values are used as the address to a lookup table. From that address, the lookup table provides a grayscale value of the pixel and surrounding pixels. See "Efficient Alias-Free Rendering Using Bit Masks and Look Up Tables", by L. Westover, G. Abram and T. Whitted, in Siggraph ACM, 19(3): pages 53-59, 1985. Most edges intersect at two points, creating either triangular or trapezoidal pieces. More complex intersections can be usually handled by representing an area covered as a combination of simple fragments, i.e. more than one lookup is performed in the table and values are added or subtracted to yield the final grayscale value. Since an edge contained within a pixel affects surrounding pixels as well, lookup tables are computed for all the immediately surrounding pixels and grayscale values are summed. One disadvantage of this method is the inability to accurately compute highly curved line segments, i.e. this method would probably not be suitable for small text due to the tight curves which compose most letters.
There are several serious limitations with the above-discussed methods of antialiasing. All the current techniques (with the exception of supersampling) are prefilters, so they operate solely on analytic or parametric curved outline data (not bitmaps or images). On the other hand, supersampling is computationally expensive, so it is not an attractive alternative. A more serious, although perhaps less academic problem is that each of the above antialiasing methods require changes to the computer scan conversion algorithm so that grayscale data can be generated. This is a very serious limitation because current graphics packages cannot be easily adapted to produce antialiased bitmaps. For example, PostScript.RTM. would be very difficult to adapt to print grayscale bitmaps because every scan conversion algorithm would have to be changed to an antialiased counterpart.
Accordingly, there is a need for implementing antialiasing in the printing process of computer systems.